package gold.digger;

import gold.utils.InputUtil;

import java.util.*;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC697 {
    public long startExecuteTime = System.currentTimeMillis();

    /*
     * 经典题目，虽然简单，但可以之后多温习
     * 适合出题考查别人
     * @return:
     */
    class Solution {
        public int findShortestSubArray(int[] nums) {
            Map<Integer, Integer> countMap = new HashMap<>();
            Map<Integer, int[]> posMap = new HashMap<>();
            for (int i = 0; i < nums.length; i++) {
                int num = nums[i];
                countMap.put(num, countMap.getOrDefault(num, 0) + 1);
                if (posMap.containsKey(num)) {
                    posMap.get(num)[1] = i;
                } else {
                    posMap.put(num, new int[]{i, -1});
                }
            }

            int maxFre = -1;
            Set<Integer> maxFreNumSet = new HashSet<>();
            for (Integer num : countMap.keySet()) {
                if (countMap.get(num) > maxFre) {
                    maxFre = countMap.get(num);
                    maxFreNumSet.clear();
                    maxFreNumSet.add(num);
                } else if (countMap.get(num) == maxFre) {
                    maxFreNumSet.add(num);
                }
            }

            int minWindow = Integer.MAX_VALUE, curWindow = 1;
            for (Integer num : maxFreNumSet) {
                if (posMap.get(num)[1] == -1) curWindow = 1;
                else curWindow = posMap.get(num)[1] - posMap.get(num)[0] + 1;
                minWindow = Math.min(minWindow, curWindow);
            }

            return minWindow;
        }
    }

    public void run() {
        Solution solution = new Solution();
        int[] arr = InputUtil.toIntegerArray("[1,2,2,3,1,4,2]");
        System.out.println(solution.findShortestSubArray(arr));
    }

    public static void main(String[] args) throws Exception {
        LC697 an = new LC697();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
